package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param root TreeNode类
 * @param o1 int整型
 * @param o2 int整型
 * @return int整型
 */
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
	// write code here
	solve(root, o1, o2)
	return ans

}

var ans = -1

func solve(root *TreeNode, o1 int, o2 int) (b1 bool, b2 bool) {
	if root == nil {
		return false, false
	}
	lb1, lb2 := solve(root.Left, o1, o2)
	rb1, rb2 := solve(root.Right, o1, o2)
	b1 = lb1 || rb1
	b2 = lb2 || rb2
	if root.Val == o1 {
		b1 = true
	} else if root.Val == o2 {
		b2 = true
	}
	if b1 && b2 && ans == -1 {
		ans = root.Val
	}
	return b1, b2
}
